package com.leet.bfs;

import java.util.*;

public class OpenTheLock {
    public char minusChar(char origin){
        char returnChar = origin;
        switch (origin){
            case '0': returnChar = '9';break;
            case '1': returnChar = '0';break;
            case '2': returnChar = '1';break;
            case '3': returnChar = '2';break;
            case '4': returnChar = '3';break;
            case '5': returnChar = '4';break;
            case '6': returnChar = '5';break;
            case '7': returnChar = '6';break;
            case '8': returnChar = '7';break;
            case '9': returnChar = '8';break;
        }
        return returnChar;
    }
    public char addChar(char origin){
        char returnChar = origin;
        switch (origin){
            case '0': returnChar = '1';break;
            case '1': returnChar = '2';break;
            case '2': returnChar = '3';break;
            case '3': returnChar = '4';break;
            case '4': returnChar = '5';break;
            case '5': returnChar = '6';break;
            case '6': returnChar = '7';break;
            case '7': returnChar = '8';break;
            case '8': returnChar = '9';break;
            case '9': returnChar = '0';break;
        }
        return returnChar;
    }
    public List<String> rotate(String num){
        List<String> ans = new ArrayList<>();
        char a0 = num.charAt(0);
        char a1 = num.charAt(1);
        char a2 = num.charAt(2);
        char a3 = num.charAt(3);
        char add0 = addChar(a0);
        char minus0 = minusChar(a0);
        char add1 = addChar(a1);
        char minus1 = minusChar(a1);
        char add2 = addChar(a2);
        char minus2 = minusChar(a2);
        char add3 = addChar(a3);
        char minus3 = minusChar(a3);
        ans.add(String.valueOf(new char[]{add0,a1,a2,a3}));
        ans.add(String.valueOf(new char[]{minus0,a1,a2,a3}));
        ans.add(String.valueOf(new char[]{a0,add1,a2,a3}));
        ans.add(String.valueOf(new char[]{a0,minus1,a2,a3}));
        ans.add(String.valueOf(new char[]{a0,a1,add2,a3}));
        ans.add(String.valueOf(new char[]{a0,a1,minus2,a3}));
        ans.add(String.valueOf(new char[]{a0,a1,a2,add3}));
        ans.add(String.valueOf(new char[]{a0,a1,a2,minus3}));
        return ans;

    }
    public int openLock(String[] deadends, String target) {
        Set<String> originList = new HashSet<>();
        originList.addAll(Arrays.asList(deadends));
        int level = 0;
        Queue<String> q = new LinkedList<>();
        q.offer("0000");
        if(originList.contains("0000")) return -1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0 ;i < size; i++){
                String front = q.poll();
                originList.add(front);
                if(target.equals(front)) return level;
                List<String> tmpList = new ArrayList<>();
                tmpList = rotate(front);
                for(String childString:tmpList){
                    if(!originList.contains(childString)){
                        q.offer(childString);
                    }
                }
            }
            level++;
        }
        return -1;
    }
}
